class Solution // 买卖股票最佳时机3
{
public:
    int maxProfit(vector<int> &prices)
    {
        const static int INF = -0x3f3f3f3f;
        int n = prices.size();
        // f是有股票，g是没有股票，i是第i天，j是交易了几次
        vector<vector<int>> f(n, vector<int>(3, INF));
        auto g = f;
        // 昨天结束没有股票，今天买入，那么g[i-1][j] -
        // prices[i]如果g[i-1][j]为INT_MIN，那么减之后会越界！
        // 所以使用-0x3f3f3f3f也就是INT_MIN的一半，那么就不会+-越界了，同理对于INT_MAX使用0x3f3f3f3f也是一样的
        // g[0][1] = g[0][2] = -0x3f3f3f3f;
        g[0][0] = 0;
        f[0][0] = -prices[0];
        for (int i = 1; i < n; ++i)
        {
            for (int j = 0; j < 3; ++j)
            {
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if (j - 1 >= 0)
                {
                    // j表示今天的交易次数，那么我昨天的交易次数就是j-1，因为j就是交易加了一次次数之后的值
                    g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i]);
                }
            }
        }
        // f表示手上有股票，所以说怎么样f也不是利润最大
        int max = INT_MIN;
        for (int i = 0; i < 3; ++i)
        {
            max = std::max(max, g[n - 1][i]);
        }
        return max;
    }
};

class Solution // 买卖股票最佳时机4
{
public:
    int maxProfit(int k, vector<int> &prices)
    {
        const static int INF = -0x3f3f3f3f;
        int n = prices.size();
        vector<vector<int>> f(n, vector<int>(k + 1, INF));
        auto g = f;
        f[0][0] = -prices[0];
        g[0][0] = 0;
        for (int i = 1; i < n; ++i)
        {
            for (int j = 0; j <= k; ++j)
            {
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if (j - 1 >= 0)
                    g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i]);
            }
        }
        int max = INT_MIN;
        for (int j = 0; j <= k; ++j)
        {
            max = std::max(max, g[n - 1][j]);
        }
        return max;
    }
};

class Solution
{
public:
    int maxSubArray(vector<int> &nums)
    {
        // if(nums.size() == 1)
        //     return nums[0];
        // int n = nums.size();
        // int max = nums[0];
        // vector<int> dp(n);
        // dp[0] = nums[0];

        int n = nums.size();
        int max = nums[0];
        vector<int> dp(n + 1);

        for (int i = 1; i <= n; ++i)
        {
            // 我i位置要的是最大和，所以前面一个位置i-1的最大和 + nums[i]就得到dp[i]
            // 但是！如果我前面一个位置的最大和是一个【负数】，那我dp[i]位置最大值要你前面一个位置值干什么，岂不是还变小了
            dp[i] = std::max(nums[i - 1], dp[i - 1] + nums[i - 1]);
            max = std::max(max, dp[i]);
        }
        return max;
    }
};

class Solution
{
public:
    int maxSubarraySumCircular(vector<int> &nums)
    {
        int n = nums.size();
        vector<int> f(n + 1);
        // f是数组内的最大和【不进行环绕】，g是数组内【最小和】--->【那么进行环绕的最大和 = sum - 数组内最小和】
        auto g = f;
        int max = nums[0];
        int min = nums[0];
        int sum = 0;
        for (int i = 1; i <= n; ++i)
        {
            sum += nums[i - 1];
            f[i] = std::max(f[i - 1] + nums[i - 1], nums[i - 1]);
            max = std::max(max, f[i]);
            g[i] = std::min(g[i - 1] + nums[i - 1], nums[i - 1]);
            min = std::min(min, g[i]);
        }
        // 进行判断！如果数组内全是负数，那么就sum - min = 0！直接返回max就行
        return ((sum == min) ? max : std::max(max, sum - min));
        // if(sum == min)
        //     return max;
        // return std::max(max,sum-min);
    }
};